/** 
 * Functions regarding the scheduler
 */
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include "scheduler.h"

schedule_list *schedule_table[10];

/**
 * Removes the next event from the schedule for processing
 */
event * next_event(schedule *s)
{
  event *next = s->head;
  s->head =  next->next;
  return next;
}

int has_event(schedule *s)
{
  return (s->head != NULL) ? 1 : 0;
}

/**
 * Add an event to a schedule
 */
schedule * join_schedules(schedule *a,  schedule *b)
{
  schedule *c = malloc(sizeof(schedule));
  //Put the event at the head of the schedule
  c->head = a->head;
  event *tmp;
  for(tmp = c->head; tmp->next != NULL; tmp = tmp->next);
  tmp->next = b->head;
  free(a);
  free(b);
  return sort_schedule(c);
}

schedule *sort_schedule(schedule *s) {
  s->head = listsort(s->head);
  return s;
}

int cmp(event *a, event *b) {
  if (a->timestamp->tv_sec == b->timestamp->tv_sec)
    {
      return (a->timestamp->tv_usec > b->timestamp->tv_usec) ? 1 : (a->timestamp->tv_usec < b->timestamp->tv_usec) ? -1 : 0;
    }
  return (a->timestamp->tv_sec > b->timestamp->tv_sec) ? 1 : (a->timestamp->tv_sec < b->timestamp->tv_sec) ? -1 : 0;  
 }

event *listsort(event *list) {
  event *p, *q, *e, *tail;
  int insize, nmerges, psize, qsize, i;
  
  /*
   * Silly special case: if `list' was passed in as NULL, return
   * NULL immediately.
   */
  if (!list)
    return NULL;

  insize = 1;

  while (1) {
    p = list;
    list = NULL;
    tail = NULL;
      
    nmerges = 0;  /* count number of merges we do in this pass */
      
    while (p) {
      nmerges++;  /* there exists a merge to be done */
      /* step `insize' places along from p */
      q = p;
      psize = 0;
      for (i = 0; i < insize; i++) {
        psize++;
        q = q->next;
        if (!q) break;
      }
            
      /* if q hasn't fallen off end, we have two lists to merge */
      qsize = insize;
            
      /* now we have two lists; merge them */
      while (psize > 0 || (qsize > 0 && q)) {
              
        /* decide whether next element of merge comes from p or q */
        if (psize == 0) {
          /* p is empty; e must come from q. */
          e = q; q = q->next; qsize--;
        } else if (qsize == 0 || !q) {
          /* q is empty; e must come from p. */
          e = p; p = p->next; psize--;
        } else if (cmp(p,q) <= 0) {
          /* First element of p is lower (or same);
           * e must come from p. */
          e = p; p = p->next; psize--;
        } else {
          /* First element of q is lower; e must come from q. */
          e = q; q = q->next; qsize--;
        }
        
        /* add the next element to the merged list */
        if (tail) {
          tail->next = e;
        } else {
          list = e;
        }
        tail = e;
      }
            
      /* now p has stepped `insize' places along, and q has too */
      p = q;
    }
	
    tail->next = NULL;
        
    /* If we have done only one merge, we're finished. */
    if (nmerges <= 1)   /* allow for nmerges==0, the empty list case */
      return list;
        
    /* Otherwise repeat, merging lists twice the size */
    insize *= 2;
  }
}

/**
 * Turn a number of events into a schedule
 */
schedule * make_schedule(int cnt, ...)
{
  va_list events;
  int i, sum;
  schedule *s = malloc(sizeof(schedule));
  if(s == NULL) {
    exit(1);
  }  
  event *tmp;
  
  //Initialize
  va_start(events, cnt);
     
  for (i = 0; i < cnt; i++) 
    {
      event *e = va_arg(events, event *);
      //Start at the head
      if(i == 0)
	{
	  s->head = e;	  
	}
      else 
	{
	  tmp->next = e;
	  //End of list
	  if(i == (cnt - 1))
	    {
	      e->next = NULL;
	    }
	}
      tmp = e;
    }
  va_end (events);             
  return s;
}
